package q145_postorderTraversal;

import CommonClass.Common.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Solution_4 {

    public List<Integer> postorderTraversal(TreeNode root) {

        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node != null){
                // 这里还要重新把node压回去
                stack.push(node);
                stack.push(null);

                if (node.right != null){
                    stack.push(node.right);
                }
                if (node.left != null){
                    stack.push(node.left);
                }
            }else {
                node = stack.pop();
                res.add(node.val);
            }

        }

        return res;
    }
}
